class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def rob2(node):
            max_left_node = 0
            max_left_without_node = 0
            max_right_node = 0
            max_right_without_node = 0
            if node.left:
                max_left_node, max_left_without_node = rob2(node.left)
            if node.right:
                max_right_node, max_right_without_node = rob2(node.right)
            max_node = max_left_without_node + max_right_without_node + node.val
            max_without_node = max(max_left_node, max_left_without_node) + max(max_right_node, max_right_without_node)
            return max_node, max_without_node

        if not root:
            return 0
        return max(rob2(root))


